{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Jumps to Reach Home"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到家的最少跳跃次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一只跳蚤的家在数轴上的位置 <code>x</code> 处。请你帮助它从位置 <code>0</code> 出发，到达它的家。</p>\n",
    "\n",
    "<p>跳蚤跳跃的规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它可以 <strong>往前</strong> 跳恰好 <code>a</code> 个位置（即往右跳）。</li>\n",
    "\t<li>它可以 <strong>往后</strong> 跳恰好 <code>b</code> 个位置（即往左跳）。</li>\n",
    "\t<li>它不能 <strong>连续</strong> 往后跳 <code>2</code> 次。</li>\n",
    "\t<li>它不能跳到任何 <code>forbidden</code> 数组中的位置。</li>\n",
    "</ul>\n",
    "\n",
    "<p>跳蚤可以往前跳 <strong>超过</strong> 它的家的位置，但是它 <strong>不能跳到负整数</strong> 的位置。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>forbidden</code> ，其中 <code>forbidden[i]</code> 是跳蚤不能跳到的位置，同时给你整数 <code>a</code>， <code>b</code> 和 <code>x</code> ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 <code>x</code> 的可行方案，请你返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11\n",
    "<b>输出：</b>-1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= forbidden.length <= 1000</code></li>\n",
    "\t<li><code>1 <= a, b, forbidden[i] <= 2000</code></li>\n",
    "\t<li><code>0 <= x <= 2000</code></li>\n",
    "\t<li><code>forbidden</code> 中所有位置互不相同。</li>\n",
    "\t<li>位置 <code>x</code> 不在 <code>forbidden</code> 中。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-jumps-to-reach-home](https://leetcode.cn/problems/minimum-jumps-to-reach-home/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-jumps-to-reach-home](https://leetcode.cn/problems/minimum-jumps-to-reach-home/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[14,4,18,1,15]\\n3\\n15\\n9', '[8,3,16,6,12,20]\\n15\\n13\\n11', '[1,6,2,14,5,17,4]\\n16\\n9\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        maxlen=2000+b+b+a+a\n",
    "        finda=[False]*maxlen\n",
    "        findb=[False]*maxlen\n",
    "        for f in forbidden:\n",
    "            #if f>=maxlen:\n",
    "            #    continue\n",
    "            finda[f]=True\n",
    "            findb[f]=True\n",
    "        q=collections.deque()\n",
    "        q.append((0,0,0))\n",
    "        while q:\n",
    "            d,local,last=q.popleft()\n",
    "            #print(d,l,r,last,local)\n",
    "            #if local<0:\n",
    "            #    continue\n",
    "            #if d>200:\n",
    "                #print(find)\n",
    "            #    return -1\n",
    "            if local==x:\n",
    "                return d\n",
    "            #if local>=maxlen:\n",
    "            #    continue\n",
    "            if last==0 and finda[local]:\n",
    "                continue\n",
    "            if last==1 and findb[local]:\n",
    "                continue\n",
    "            if last==0:\n",
    "                finda[local]=True\n",
    "            else:\n",
    "                findb[local]=True\n",
    "            if local+a<maxlen:\n",
    "                q.append((d+1,local+a,0))\n",
    "            if local-b>0 and last==0:\n",
    "                q.append((d+1,local-b,1))\n",
    "        #print(find)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q = deque([[0, 1, 0]])\n",
    "        visited = set([0])\n",
    "        lower = 0\n",
    "        upper = max(max(forbidden) + a, x) + b\n",
    "        forbiddenset = set(forbidden)\n",
    "        while q:\n",
    "            position, direction, step = q.popleft()\n",
    "            if position == x:\n",
    "                return step\n",
    "            nextPoition = position + a\n",
    "            nextDirection = 1\n",
    "            if lower <= nextPoition <= upper and nextPoition not in visited and nextPoition not in forbiddenset:\n",
    "                visited.add(nextPoition * nextDirection)\n",
    "                q.append([nextPoition, nextDirection, step + 1])\n",
    "            if direction == 1:\n",
    "                nextPoition = position - b\n",
    "                nextDirection = -1\n",
    "                if lower <= nextPoition <= upper and nextPoition not in visited and nextPoition not in forbiddenset:\n",
    "                    visited.add(nextPoition * nextDirection)\n",
    "                    q.append([nextPoition, nextDirection, step + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "#         s=set(forbidden)\n",
    "#         q=deque([(0,1)])\n",
    "#         vis={(0,1)}\n",
    "#         ans=0\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i,k=q.popleft()\n",
    "#                 if i==x:\n",
    "#                     return ans\n",
    "#                  nxt=[(i+a,1)]\n",
    "#                 if k&1:\n",
    "#                     nxt.append((i-b,0))\n",
    "#                 for j,k in nxt:\n",
    "#                     if 0<=j<6000 and j not in s and (j,k) not in vis:\n",
    "#                         q.append((j,k))\n",
    "#                         vis.add((j,k))\n",
    "#             ans+=1\n",
    "#         return -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        forbiddenSet = set(forbidden)\n",
    "        while q:\n",
    "            position, direction, step = q.popleft()\n",
    "            if position == x:\n",
    "                return step\n",
    "            nextPosition = position + a\n",
    "            nextDirection = 1\n",
    "            if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                visited.add(nextPosition * nextDirection)\n",
    "                q.append([nextPosition, nextDirection, step + 1])\n",
    "            if direction == 1:\n",
    "                nextPosition = position - b\n",
    "                nextDirection = -1\n",
    "                if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                    visited.add(nextPosition * nextDirection)\n",
    "                    q.append([nextPosition, nextDirection, step + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "定义状态(idx, cnt), idx表示当前位置，cnt表示连续往后面跳了几次\n",
    "- 注意设定上界, 要保证超过x还能跳回来\n",
    "- 下界不能够跳成负数\n",
    "- 采用vis记录状态\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, target: int) -> int:\n",
    "        up = max(max(forbidden) + a, target) + b\n",
    "        forbidden = Counter(forbidden)\n",
    "        q = deque([(0, 0)])\n",
    "        vis = set()\n",
    "        step = 0\n",
    "        while q:\n",
    "            m = len(q)\n",
    "            for _ in range(m):\n",
    "                x, cnt = q.popleft()\n",
    "                if x == target:\n",
    "                    return step\n",
    "                dx = x + a\n",
    "                if 0 <= dx <= up and (dx, 0) not in vis and dx not in forbidden:\n",
    "                    vis.add((dx, 0))\n",
    "                    q.append((dx, 0))\n",
    "                dx = x - b\n",
    "                if 0 <= dx <= up and (dx, cnt + 1) not in vis and dx not in forbidden:\n",
    "                    if cnt < 1:\n",
    "                        vis.add((dx, cnt + 1))\n",
    "                        q.append((dx, cnt + 1))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        upper=max(max(forbidden)+a,x)+b\n",
    "        forbidden=set(forbidden)\n",
    "        stack=collections.deque()\n",
    "        stack.append([0,0,0])\n",
    "        vis=set()\n",
    "        \n",
    "        if 0 in forbidden:\n",
    "            return -1\n",
    "        vis.add((0,0))\n",
    "        while stack:\n",
    "            d,cur,backcount=stack.popleft()\n",
    "            #print(d,cur)\n",
    "            #if d >4000:\n",
    "           #     return -1\n",
    "\n",
    "          #  if cur in vis:\n",
    "            #    continue\n",
    "          #  vis.add(cur)\n",
    "            if cur==x:\n",
    "                return d\n",
    "            nex=cur+a\n",
    "            if nex not in forbidden and nex>=0  and (nex,0) not in vis and nex<=upper:\n",
    "                stack.append([d+1,nex,0])\n",
    "                vis.add((nex,0))\n",
    "            nex=cur-b\n",
    "            if nex not in forbidden and nex>=0  and backcount==0 and (nex,1) not in vis and nex<=upper:\n",
    "                stack.append([d+1,nex,1])    \n",
    "                vis.add((nex,1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "#         s=set(forbidden)\n",
    "#         q=deque([(0,1)])\n",
    "#         vis={(0,1)}\n",
    "#         ans=0\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i,k=q.popleft()\n",
    "#                 if i==x:\n",
    "#                     return ans\n",
    "#                  nxt=[(i+a,1)]\n",
    "#                 if k&1:\n",
    "#                     nxt.append((i-b,0))\n",
    "#                 for j,k in nxt:\n",
    "#                     if 0<=j<6000 and j not in s and (j,k) not in vis:\n",
    "#                         q.append((j,k))\n",
    "#                         vis.add((j,k))\n",
    "#             ans+=1\n",
    "#         return -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        forbiddenSet = set(forbidden)\n",
    "        while q:\n",
    "            position, direction, step = q.popleft()\n",
    "            if position == x:\n",
    "                return step\n",
    "            nextPosition = position + a\n",
    "            nextDirection = 1\n",
    "            if 0 <= nextPosition <= 6000 and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                visited.add(nextPosition * nextDirection)\n",
    "                q.append([nextPosition, nextDirection, step + 1])\n",
    "            if direction == 1:\n",
    "                nextPosition = position - b\n",
    "                nextDirection = -1\n",
    "                if 0 <= nextPosition <= 6000 and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                    visited.add(nextPosition * nextDirection)\n",
    "                    q.append([nextPosition, nextDirection, step + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "#         s=set(forbidden)\n",
    "#         q=deque([(0,1)])\n",
    "#         vis={(0,1)}\n",
    "#         ans=0\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i,k=q.popleft()\n",
    "#                 if i==x:\n",
    "#                     return ans\n",
    "#                  nxt=[(i+a,1)]\n",
    "#                 if k&1:\n",
    "#                     nxt.append((i-b,0))\n",
    "#                 for j,k in nxt:\n",
    "#                     if 0<=j<6000 and j not in s and (j,k) not in vis:\n",
    "#                         q.append((j,k))\n",
    "#                         vis.add((j,k))\n",
    "#             ans+=1\n",
    "#         return -1\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        forbiddenSet = set(forbidden)\n",
    "        while q:\n",
    "            position, direction, step = q.popleft()\n",
    "            if position == x:\n",
    "                return step\n",
    "            nextPosition = position + a\n",
    "            nextDirection = 1\n",
    "            if 0 <= nextPosition <= 6000 and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                visited.add(nextPosition * nextDirection)\n",
    "                q.append([nextPosition, nextDirection, step + 1])\n",
    "            if direction == 1:\n",
    "                nextPosition = position - b\n",
    "                nextDirection = -1\n",
    "                if 0 <= nextPosition <= 6000 and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "                    visited.add(nextPosition * nextDirection)\n",
    "                    q.append([nextPosition, nextDirection, step + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "定义状态(idx, cnt), idx表示当前位置，cnt表示连续往后面跳了几次\n",
    "- 注意设定上界, 要保证超过x还能跳回来\n",
    "- 下界不能够跳成负数\n",
    "- 采用vis记录状态\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, target: int) -> int:\n",
    "        up = max(forbidden) + target + a + b\n",
    "        forbidden = Counter(forbidden)\n",
    "        q = deque([(0, 0)])\n",
    "        vis = set()\n",
    "        step = 0\n",
    "        while q:\n",
    "            m = len(q)\n",
    "            for _ in range(m):\n",
    "                x, cnt = q.popleft()\n",
    "                if x == target:\n",
    "                    return step\n",
    "                dx = x + a\n",
    "                if 0 <= dx < up and (dx, 0) not in vis and dx not in forbidden:\n",
    "                    vis.add((dx, 0))\n",
    "                    q.append((dx, 0))\n",
    "                dx = x - b\n",
    "                if 0 <= dx < up and (dx, cnt + 1) not in vis and dx not in forbidden:\n",
    "                    if cnt < 1:\n",
    "                        vis.add((dx, cnt + 1))\n",
    "                        q.append((dx, cnt + 1))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        s=set(forbidden)\n",
    "        q=deque([(0,1)])\n",
    "        vis={(0,1)}\n",
    "        ans=0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i,k=q.popleft()\n",
    "                if i==x:\n",
    "                    return ans\n",
    "                nxt=[(i+a,1)]\n",
    "                if k&1:\n",
    "                    nxt.append((i-b,0))\n",
    "                for j,k in nxt:\n",
    "                    if 0<=j<6000 and j not in s and (j,k) not in vis:\n",
    "                        q.append((j,k))\n",
    "                        vis.add((j,k))\n",
    "            ans+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        s=set(forbidden)\n",
    "        q=deque([(0,1)])\n",
    "        vis={(0,1)}\n",
    "        ans=0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i,k=q.popleft()\n",
    "                if i==x:\n",
    "                    return ans\n",
    "                nxt=[(i+a,1)]\n",
    "                if k&1:\n",
    "                    nxt.append((i-b,0))\n",
    "                for j,k in nxt:\n",
    "                    if 0<=j<6000 and j not in s and (j,k) not in vis:\n",
    "                        q.append((j,k))\n",
    "                        vis.add((j,k))\n",
    "            ans+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        if not x:\n",
    "            return 0\n",
    "        if a in forbidden:\n",
    "            return -1\n",
    "        step = 0\n",
    "        q = deque()\n",
    "        q.append((a, False))\n",
    "        vis = set()\n",
    "        vis.add((a, False))\n",
    "        l = 7500\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                i, back = q.popleft()\n",
    "                if i == x:\n",
    "                    return step + 1\n",
    "                if not back and i - b > 0 and (i - b, True) not in vis and i - b not in forbidden:\n",
    "                    q.append((i - b, True))\n",
    "                    vis.add((i - b, True))\n",
    "                if i + a < l and (i + a, False) not in vis and i + a not in forbidden:\n",
    "                    q.append((i + a, False))\n",
    "                    vis.add((i + a, False))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q = deque()\n",
    "        forbidden = set(forbidden)\n",
    "        start = (0, 0)\n",
    "        q.append(start)\n",
    "        step = 0\n",
    "        l, r = 0, 7500\n",
    "        vis = set()\n",
    "        vis.add(start)\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            for _ in range(s):\n",
    "                pos, flag = q.popleft()\n",
    "                if pos == x:\n",
    "                    return step\n",
    "                front = pos + a\n",
    "                back = pos - b\n",
    "                if front <= r and front not in forbidden and (front, 0) not in vis:\n",
    "                    vis.add((front, 0))\n",
    "                    q.append((front, 0))\n",
    "                if back >= l and not flag and back not in forbidden and (back, 1) not in vis:\n",
    "                    vis.add((back, 1))\n",
    "                    q.append((back, 1))\n",
    "            step += 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        self.x = x\n",
    "        self.dp = {}\n",
    "        for i in forbidden:\n",
    "            self.dp[(i,0)] = -1\n",
    "            self.dp[(i,1)] = -1\n",
    "        remain = [[a, 1, 1]]\n",
    "        c = 1\n",
    "        while remain:\n",
    "            # print(remain)\n",
    "            cur, rev, c = remain.pop(0)\n",
    "            if (cur, rev) in self.dp:\n",
    "                continue\n",
    "            if cur > 6000:\n",
    "                continue\n",
    "            if cur < 0:\n",
    "                continue\n",
    "            self.dp[(cur, rev)] = c\n",
    "            if cur == x:\n",
    "                break\n",
    "            if not rev:\n",
    "                remain.append([cur+ a,1,c+1])\n",
    "                continue\n",
    "            # if cur - b > x:\n",
    "            #     remain.extend([[ cur-b,0,c+1]])\n",
    "            # else:\n",
    "            remain.extend([[cur+a,1,c+1],[ cur-b,0,c+1]])\n",
    "            \n",
    "        # print(self.dp)\n",
    "        if (x, 0) in self.dp:\n",
    "            return self.dp[(x, 0)]\n",
    "        if (x, 1) in self.dp:\n",
    "            return self.dp[(x, 1)]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, fbi: List[int], a: int, b: int, x: int) -> int:\n",
    "        fbi = set(fbi)\n",
    "        dist = defaultdict(lambda x: inf)\n",
    "        q = deque([(0, True)])\n",
    "        dist[(0, True)] = 0\n",
    "        while q:\n",
    "            u, can_left = q.popleft()\n",
    "            if u == x: return dist[(u, can_left)]\n",
    "            right = u + a\n",
    "            if right not in fbi and right < 6000 and (right, True) not in dist:\n",
    "                dist[(right, True)] = dist[(u, can_left)] + 1\n",
    "                q.append((right, True))\n",
    "            left = u - b\n",
    "            if can_left and left not in fbi and left >= 0 and (left, False) not in dist:\n",
    "                dist[(left, False)] = dist[(u, can_left)] + 1\n",
    "                q.append((left, False))\n",
    "        return -1\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        d = Counter(forbidden) # cannot jump position\n",
    "        q = deque()\n",
    "        q.append((0, False))\n",
    "        dist = [-1] * (100010)\n",
    "        dist[0] = 0\n",
    "        vis = Counter()\n",
    "        vis[(0, False)] = 1\n",
    "        ans = 0\n",
    "        while len(q):\n",
    "            t, flg = q.popleft()\n",
    "            if t == x:\n",
    "                return dist[x] \n",
    "            nxt = [(t + a, False)]\n",
    "            if not flg:\n",
    "                nxt.append((t - b, True))\n",
    "            for j, k in nxt:\n",
    "                if 0 <= j < 6000 and j not in d and (j, k) not in vis:\n",
    "                    q.append((j, k))\n",
    "                    dist[j] = dist[t] + 1\n",
    "                    vis[(j, k)] = 1\n",
    "        return -1\n",
    "                \n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        dic=set(forbidden)\n",
    "        vis={}\n",
    "        ans=-1\n",
    "        q=queue.Queue()\n",
    "        q.put([0,1])\n",
    "        vis[(0,1)]=True\n",
    "        cnt=0\n",
    "        while q.qsize()!=0:\n",
    "            size=q.qsize()\n",
    "            for i in range(size):\n",
    "                t=q.get()\n",
    "                if t[0]==x:\n",
    "                    ans=cnt\n",
    "                    break\n",
    "                nxta=t[0]+a\n",
    "                nxtb=t[0]-b\n",
    "                if nxta not in dic and nxta<10**4 and (nxta,1) not in vis:\n",
    "                    q.put([nxta,1])\n",
    "                    vis[(nxta,1)]=True\n",
    "                if nxtb not in dic and nxtb>=0 and t[1]!=-1 and (nxtb,-1) not in vis:\n",
    "                    q.put([nxtb,-1])\n",
    "                    vis[(nxtb,-1)]=True\n",
    "            cnt+=1\n",
    "            if ans!=-1:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        vis = set(forbidden)\n",
    "        vis.add(0)\n",
    "        q = deque([(0, 0, True), (0, 0, False)])\n",
    "        while q:\n",
    "            curr, step, forward = q.popleft()\n",
    "            if curr == x:\n",
    "                return step\n",
    "            if curr > x + 10 * b:\n",
    "                continue\n",
    "            if forward and (nxt := curr - b) >= 0 and nxt not in vis:\n",
    "                vis.add(nxt)\n",
    "                q.append((nxt, step + 1, False))\n",
    "            if (nxt := curr + a) not in vis:\n",
    "                vis.add(nxt)\n",
    "                q.append((nxt, step + 1, True))\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        # n = len(forbidden)\n",
    "        n = x+a+b*5+1\n",
    "        vis = [0]*n\n",
    "        for p in forbidden:\n",
    "            try:\n",
    "                vis[p] = 1\n",
    "            except:\n",
    "                pass\n",
    "        que = [[0,0,0]]\n",
    "        ne = 0\n",
    "        while ne < len(que):\n",
    "            cur, pre, t = que[ne]\n",
    "            ne += 1\n",
    "            if cur < 0 or cur >= n or vis[cur]:\n",
    "                continue\n",
    "            vis[cur] = 1\n",
    "\n",
    "            if cur == x:\n",
    "                return t\n",
    "            if not pre:\n",
    "                que.append([cur-b, 1, t+1])\n",
    "            que.append([cur+a, 0, t+1])\n",
    "        return -1\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        bitmap = [0]*110000\n",
    "        for pos in forbidden: bitmap[pos] = -1\n",
    "        que = []\n",
    "        heapq.heappush(que, 0)\n",
    "        if x == 0: return 0\n",
    "        while que:\n",
    "            cur = heapq.heappop(que)\n",
    "            # print(cur, que)\n",
    "            if cur > 100000: break\n",
    "            # if cur-b > x:  # 不对， 互质的两个数29, 97， 每次叠加相当于-68，所以就算cur-b>x，经过多次叠加，会再次<x\n",
    "                # print(\"drop\", cur)\n",
    "                # continue # 不会跳到x了,\n",
    "                            \n",
    "            if bitmap[cur+a] == 0:\n",
    "                if cur+a-b > 0 and bitmap[cur+a-b] == 0:\n",
    "                    bitmap[cur+a-b] = bitmap[cur] + 2\n",
    "                    heapq.heappush(que, cur+a-b)\n",
    "                bitmap[cur+a] = bitmap[cur] + 1\n",
    "                heapq.heappush(que, cur+a)\n",
    "            if bitmap[x] > 0: break\n",
    "        return -1 if bitmap[x] == 0 else bitmap[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        max_l = 10000\n",
    "        is_forbidden = [False] * max_l\n",
    "        count = [[max_l, max_l] for _ in range(max_l)]\n",
    "        count[0][0] = 0\n",
    "        q, h = [(0, 0)], 0\n",
    "        for num in forbidden:\n",
    "            is_forbidden[num] = True\n",
    "\n",
    "        while h < len(q):\n",
    "            (now, state), h = q[h], h + 1\n",
    "            if now == x:\n",
    "                return count[now][state]\n",
    "            if state == 0:\n",
    "                if now - b >= 0 and count[now][state] + 1 < count[now - b][1] and not is_forbidden[now - b]:\n",
    "                    count[now - b][1] = count[now][state] + 1\n",
    "                    q.append([now - b, 1])\n",
    "                \n",
    "            if now + a < max_l and count[now][state] + 1 < count[now + a][0] and not is_forbidden[now + a]:\n",
    "                count[now + a][0] = count[now][state] + 1\n",
    "                q.append([now + a, 0])\n",
    "        \n",
    "        return -1\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from math import inf\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int: # BFS 试试\n",
    "        forbidden = set(forbidden)\n",
    "        dis = defaultdict(int)\n",
    "        dis[(0, 1)] = 0 # dis[(i, j)]，i表示位置，j=1表示可以往前跑和往后跑，j=0只能往前跑\n",
    "\n",
    "        q = [(0, 1)]\n",
    "        step = 0\n",
    "\n",
    "        while q:\n",
    "            # print(q, dis)\n",
    "            temp = q\n",
    "            q = []\n",
    "            for i, j in temp:\n",
    "                if i == x:\n",
    "                    return step\n",
    "                if j == 0: # 只能往前跑\n",
    "                    newI = i + a\n",
    "                    if newI not in forbidden and (newI, 1) not in dis and newI < 10000:\n",
    "                        q.append((newI, 1))\n",
    "                        dis[(newI, 1)] = step + 1\n",
    "                else:\n",
    "                    newI = i + a\n",
    "                    if newI not in forbidden and (newI, 1) not in dis and newI < 10000:\n",
    "                        q.append((newI, 1))\n",
    "                        dis[(newI, 1)] = step + 1\n",
    "                    newI = i - b\n",
    "                    if newI >= 0 and newI not in forbidden and (newI, 0) not in dis:\n",
    "                        q.append((newI, 0))\n",
    "                        dis[(newI, 0)] = step + 1\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        f = set(forbidden)\n",
    "        ub = 10000\n",
    "        q = deque([(0, 0, 0)])\n",
    "        seen = set([(0, 0)])\n",
    "        while q:\n",
    "            d, node, v = q.popleft()\n",
    "            if node == x:\n",
    "                return d\n",
    "            if node + a < ub and node + a not in f and (node + a, 1) not in seen:\n",
    "                seen.add((node + a, 1))\n",
    "                q.append((d + 1, node + a, 1))\n",
    "            if v and node - b > 0 and node - b not in f and (node - b, 0) not in seen:\n",
    "                seen.add((node - b, 0))\n",
    "                q.append((d + 1, node - b, 0))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q = deque([(0, False)])\n",
    "        f = set(forbidden)\n",
    "        MAXL = 10000\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        vis.add((0, False))\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                i, back = q.popleft()\n",
    "                if i == x:\n",
    "                    return ans\n",
    "                if back is False:\n",
    "                    for di in (a, -b):\n",
    "                        new_i = i + di\n",
    "                        if 0 <= new_i <= MAXL and (new_i, di < 0) not in vis and new_i not in f:\n",
    "                            vis.add((new_i, di < 0))\n",
    "                            q.append((new_i, False if di > 0 else True))\n",
    "                else:\n",
    "                    new_i = i + a\n",
    "                    if 0 <= new_i <= MAXL and (new_i, False) not in vis and new_i not in f:\n",
    "                        vis.add((new_i, False))\n",
    "                        q.append((new_i, False))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, tar: int) -> int:\n",
    "        # 记忆化+bfs\n",
    "        up = max(forbidden) + 2 * b+a\n",
    "        fb = set(forbidden)\n",
    "        q = deque([(0, 0)])\n",
    "        vis = set([(0, 0)])\n",
    "        step = 0\n",
    "        while q:\n",
    "            m = len(q)\n",
    "            for _ in range(m):\n",
    "                x, t = q.popleft()\n",
    "                if x > 10000 or x < 0: continue\n",
    "                if x == tar: return step\n",
    "                if t == 0:\n",
    "                    if x + a not in fb and (x + a, t) not in vis:\n",
    "                        q.append((x + a, t))\n",
    "                        vis.add((x + a, t))\n",
    "                    if x - b not in fb and (x - b, t + 1) not in vis:\n",
    "                        q.append((x - b, t + 1))\n",
    "                        vis.add((x - b, t + 1))\n",
    "                elif t == 1:\n",
    "                    if x + a not in fb and (x + a, t - 1) not in vis:\n",
    "                        q.append((x + a, t - 1))\n",
    "                        vis.add((x + a, t - 1))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "        \n",
    "        # end = x + (a + b) * 3\n",
    "        end = max(x, max(forbidden)) + a + b\n",
    "        dps = [inf] * (end + 1)\n",
    "        \n",
    "        for ban in forbidden:\n",
    "            if ban <= end: dps[ban] = -1\n",
    "        \n",
    "        def dp(root: int, step: int, isBackJump: bool):\n",
    "            if dps[x] != inf: return\n",
    "            if root <= 0 or root > end or dps[root] <= step: return\n",
    "            if not isBackJump or root == x: dps[root] = step\n",
    "            dp(root + a, step + 1, False)\n",
    "            if not isBackJump: dp(root - b, step + 1, True)\n",
    "\n",
    "        dp(a, 1, False)\n",
    "        \n",
    "\n",
    "        return -1 if dps[x] == inf else dps[x]\n",
    "\n",
    "        # q = queue.Queue()\n",
    "\n",
    "        # end = x + (a + b) * 3\n",
    "        # dps = [inf] * (end + 1)\n",
    "        # dpsBack = [inf] * (end + 1)\n",
    "\n",
    "        # for ban in forbidden:\n",
    "        #     dps[ban] = -1\n",
    "        #     dps[ban] = -1\n",
    "\n",
    "        # q.put([0, 0, False])\n",
    "\n",
    "        # while q.qsize():\n",
    "        #     for _ in range(q.qsize()):\n",
    "        #         root,step,isBack = q.get()\n",
    "        #         if isBack:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #         else:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #             if root - b > 0 and dpsBack[root - b] != -1 and dpsBack[root - b] > step + 1:\n",
    "        #                 dpsBack[root - b] = step + 1\n",
    "        #                 q.put([root - b, step + 1, True])\n",
    "        # res = min(dps[x], dpsBack[x])\n",
    "        # return -1 if res == inf else res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        # forbiddenSet = set(forbidden)\n",
    "        # while q:\n",
    "        #     position, direction, step = q.popleft()\n",
    "        #     if position == x:\n",
    "        #         return step\n",
    "        #     nextPosition = position + a\n",
    "        #     nextDirection = 1\n",
    "        #     if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #         visited.add(nextPosition * nextDirection)\n",
    "        #         q.append([nextPosition, nextDirection, step + 1])\n",
    "        #     if direction == 1:\n",
    "        #         nextPosition = position - b\n",
    "        #         nextDirection = -1\n",
    "        #         if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #             visited.add(nextPosition * nextDirection)\n",
    "        #             q.append([nextPosition, nextDirection, step + 1])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = [[0, 0] for _ in range(6010)]\n",
    "    \n",
    "    def dp(self, forbiddenSet, pos, a, b, x, f=0):\n",
    "        if pos == x:\n",
    "            return 0\n",
    "        if pos >= 6000:\n",
    "            return -1\n",
    "        if (b <= a and pos > x + b) or pos < 0 or pos in forbiddenSet:\n",
    "            return -1\n",
    "        if self.memo[pos][f] != 0:\n",
    "            return self.memo[pos][f]\n",
    "        self.memo[pos][f] = -1\n",
    "        res_a, res_b = 0, 0\n",
    "        res_a = self.dp(forbiddenSet, pos + a, a, b, x)\n",
    "        if f == 1:\n",
    "            res_b = -1\n",
    "        else:\n",
    "            res_b = self.dp(forbiddenSet, pos - b, a, b, x, 1)\n",
    "        if res_a == -1 and res_b == -1:\n",
    "            self.memo[pos][f] = -1\n",
    "        elif res_a == -1:\n",
    "            self.memo[pos][f] = res_b + 1\n",
    "        elif res_b == -1:\n",
    "            self.memo[pos][f] = res_a + 1\n",
    "        else:\n",
    "            self.memo[pos][f] = min(res_a, res_b) + 1\n",
    "        return self.memo[pos][f]\n",
    "    \n",
    "    def minimumJumps(self, forbidden, a, b, x):\n",
    "        forbiddenSet = set(forbidden)\n",
    "        \n",
    "        res = self.dp(forbiddenSet, 0, a, b, x)\n",
    "        for i, k in enumerate(self.memo):\n",
    "            if k not in [[0, 0], [0, -1], [-1, 0], [-1, -1]]:\n",
    "                print(i, k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self,forbidden:List[int], a:int,b:int,x:int)->int:\n",
    "        self.forbidden=set(forbidden)\n",
    "        self.ans=-1\n",
    "        self.dfs(a,b,x,0,0,0)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self,a,b,x,num,cnt,back):\n",
    "        if self.ans<0:   #6000是往右探索的最大值，x最大为2000\n",
    "            if num==x:  #第一次遍历到x时的次数即为结果，暂存结果，不再递归\n",
    "                self.ans=cnt\n",
    "                return\n",
    "            p1=num+a\n",
    "            if p1<=6000 and p1 not in self.forbidden:\n",
    "                self.forbidden.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归\n",
    "                self.dfs(a,b,x,num+a, cnt+1, 0)\n",
    "            p2=num-b\n",
    "            if p2>=0 and num-b not in self.forbidden and back != 1: #若back为1说明上次就是往后跳的\n",
    "                self.dfs(a,b,x,num-b, cnt+1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self,forbidden:List[int], a:int,b:int,x:int)->int:\n",
    "        self.forbidden=set(forbidden)\n",
    "        self.ans=-1\n",
    "        self.dfs(a,b,x,0,0,0)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self,a,b,x,num,cnt,back):\n",
    "        if self.ans<0:   #6000是往右探索的最大值，x最大为2000\n",
    "            if num==x:  #第一次遍历到x时的次数即为结果，暂存结果，不再递归\n",
    "                self.ans=cnt\n",
    "                return\n",
    "            p1=num+a\n",
    "            if p1<=6000 and p1 not in self.forbidden:\n",
    "                self.forbidden.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归\n",
    "                self.dfs(a,b,x,num+a, cnt+1, 0)\n",
    "            p2=num-b\n",
    "            if p2>=0 and num-b not in self.forbidden and back != 1: #若back为1说明上次就是往后跳的\n",
    "                self.dfs(a,b,x,num-b, cnt+1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self,forbidden:List[int], a:int,b:int,x:int)->int:\n",
    "        self.visited=set(forbidden)\n",
    "        self.ans=-1\n",
    "        self.visited.add(0)\n",
    "        self.dfs(a,b,x,0,0,0)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self,a,b,x,num,cnt,back):\n",
    "        if self.ans<0:   #6000是往右探索的最大值，x最大为2000\n",
    "            if num==x:  #第一次遍历到x时的次数即为结果，暂存结果，不再递归\n",
    "                self.ans=cnt\n",
    "                return\n",
    "            p1=num+a\n",
    "            if p1<=6000 and p1 not in self.visited:\n",
    "                self.visited.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归\n",
    "                self.dfs(a,b,x,num+a, cnt+1, 0)\n",
    "            p2=num-b\n",
    "            if p2>=0 and num-b not in self.visited and back != 1: #若back为1说明上次就是往后跳的\n",
    "                self.dfs(a,b,x,num-b, cnt+1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "\n",
    "        end = x + (a + b) * 3\n",
    "        dps = [inf] * (end + 1)\n",
    "        \n",
    "        for ban in forbidden:\n",
    "            if ban <= end: dps[ban] = -1\n",
    "        \n",
    "        def dp(root: int, step: int, isBackJump: bool):\n",
    "            if root <= 0 or root > end: return\n",
    "            if dps[root] <= step: return\n",
    "            if not isBackJump or root == x: dps[root] = step\n",
    "            dp(root + a, step + 1, False)\n",
    "            if not isBackJump: dp(root - b, step + 1, True)\n",
    "\n",
    "        dp(a, 1, False)\n",
    "        \n",
    "\n",
    "        return -1 if dps[x] == inf else dps[x]\n",
    "\n",
    "        # q = queue.Queue()\n",
    "\n",
    "        # end = x + (a + b) * 3\n",
    "        # dps = [inf] * (end + 1)\n",
    "        # dpsBack = [inf] * (end + 1)\n",
    "\n",
    "        # for ban in forbidden:\n",
    "        #     dps[ban] = -1\n",
    "        #     dps[ban] = -1\n",
    "\n",
    "        # q.put([0, 0, False])\n",
    "\n",
    "        # while q.qsize():\n",
    "        #     for _ in range(q.qsize()):\n",
    "        #         root,step,isBack = q.get()\n",
    "        #         if isBack:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #         else:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #             if root - b > 0 and dpsBack[root - b] != -1 and dpsBack[root - b] > step + 1:\n",
    "        #                 dpsBack[root - b] = step + 1\n",
    "        #                 q.put([root - b, step + 1, True])\n",
    "        # res = min(dps[x], dpsBack[x])\n",
    "        # return -1 if res == inf else res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        # forbiddenSet = set(forbidden)\n",
    "        # while q:\n",
    "        #     position, direction, step = q.popleft()\n",
    "        #     if position == x:\n",
    "        #         return step\n",
    "        #     nextPosition = position + a\n",
    "        #     nextDirection = 1\n",
    "        #     if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #         visited.add(nextPosition * nextDirection)\n",
    "        #         q.append([nextPosition, nextDirection, step + 1])\n",
    "        #     if direction == 1:\n",
    "        #         nextPosition = position - b\n",
    "        #         nextDirection = -1\n",
    "        #         if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #             visited.add(nextPosition * nextDirection)\n",
    "        #             q.append([nextPosition, nextDirection, step + 1])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "\n",
    "        end = x + (a + b) * 3\n",
    "        dps = [inf] * (end + 1)\n",
    "        \n",
    "        for ban in forbidden:\n",
    "            if ban <= end: dps[ban] = -1\n",
    "        \n",
    "        def dp(root: int, step: int, isBackJump: bool):\n",
    "            if dps[x] != inf: return\n",
    "            if root <= 0 or root > end: return\n",
    "            if dps[root] <= step: return\n",
    "            if not isBackJump or root == x: dps[root] = step\n",
    "            dp(root + a, step + 1, False)\n",
    "            if not isBackJump: dp(root - b, step + 1, True)\n",
    "\n",
    "        dp(a, 1, False)\n",
    "        \n",
    "\n",
    "        return -1 if dps[x] == inf else dps[x]\n",
    "\n",
    "        # q = queue.Queue()\n",
    "\n",
    "        # end = x + (a + b) * 3\n",
    "        # dps = [inf] * (end + 1)\n",
    "        # dpsBack = [inf] * (end + 1)\n",
    "\n",
    "        # for ban in forbidden:\n",
    "        #     dps[ban] = -1\n",
    "        #     dps[ban] = -1\n",
    "\n",
    "        # q.put([0, 0, False])\n",
    "\n",
    "        # while q.qsize():\n",
    "        #     for _ in range(q.qsize()):\n",
    "        #         root,step,isBack = q.get()\n",
    "        #         if isBack:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #         else:\n",
    "        #             if root + a < end and dps[root + a] != -1 and dps[root + a] > step + 1:\n",
    "        #                 dps[root + a] = step + 1\n",
    "        #                 q.put([root + a, step + 1, False])\n",
    "        #             if root - b > 0 and dpsBack[root - b] != -1 and dpsBack[root - b] > step + 1:\n",
    "        #                 dpsBack[root - b] = step + 1\n",
    "        #                 q.put([root - b, step + 1, True])\n",
    "        # res = min(dps[x], dpsBack[x])\n",
    "        # return -1 if res == inf else res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # q, visited = deque([[0, 1, 0]]), set([0])\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        # forbiddenSet = set(forbidden)\n",
    "        # while q:\n",
    "        #     position, direction, step = q.popleft()\n",
    "        #     if position == x:\n",
    "        #         return step\n",
    "        #     nextPosition = position + a\n",
    "        #     nextDirection = 1\n",
    "        #     if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #         visited.add(nextPosition * nextDirection)\n",
    "        #         q.append([nextPosition, nextDirection, step + 1])\n",
    "        #     if direction == 1:\n",
    "        #         nextPosition = position - b\n",
    "        #         nextDirection = -1\n",
    "        #         if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:\n",
    "        #             visited.add(nextPosition * nextDirection)\n",
    "        #             q.append([nextPosition, nextDirection, step + 1])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        if a == b:\n",
    "            maxlen = x\n",
    "        elif a > b:\n",
    "            maxlen = x + b \n",
    "        else:\n",
    "            maxlen = max(max(forbidden)+a+b, x)\n",
    "        visit = set()\n",
    "        def dfs(pos, step, direction):\n",
    "            if pos > maxlen or pos < 0 or pos * direction in visit:\n",
    "                return -1\n",
    "            visit.add(pos*direction)\n",
    "            if pos in forbidden:\n",
    "                return -1 \n",
    "            if pos == x:\n",
    "                return step \n",
    "            right = dfs(pos+a, step+1, 1)\n",
    "            if right != -1:\n",
    "                return right\n",
    "            if direction == 1:\n",
    "                left = dfs(pos-b, step+1, -1)\n",
    "                if left != -1:\n",
    "                    return left \n",
    "            return -1\n",
    "            \n",
    "        return dfs(0,0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        self.key = -1\n",
    "\n",
    "        def dfs(cur, cnt, back):\n",
    "            if self.key < 0 and 0 <= cur <= 6000:\n",
    "                if cur == x:\n",
    "                    self.key = cnt\n",
    "                    return\n",
    "\n",
    "                if cur + a <= 6000 and cur + a not in forbidden:\n",
    "                    forbidden.add(cur + a)\n",
    "                    dfs(cur + a, cnt + 1, 0)\n",
    "                \n",
    "                if cur - b > 0 and cur - b not in forbidden and back != 1:\n",
    "                    dfs(cur - b, cnt + 1, 1)\n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return self.key\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "        end = x + (a + b) * 3\n",
    "        dps = [0] * (end + 1)\n",
    "        dpsBackJump = [0] * (end + 1)\n",
    "        \n",
    "        for ban in forbidden:\n",
    "            if ban <= end: dpsBackJump[ban] = dps[ban] = -1\n",
    "        \n",
    "        # def dp(root: int, step: int, isBackJump: bool):\n",
    "        #     if root < 0 or root > end or dps[root] == -1: return\n",
    "        #     # if dps[root] > 0 and dps[root] < step: return\n",
    "        #     if dps[root] <= step: return\n",
    "        #     dps[root] = step\n",
    "        #     dp(root + a, step + 1, False)\n",
    "        #     if not isBackJump: dp(root - b, step + 1, True)\n",
    "\n",
    "        def dpBackJump(root: int, step: int):\n",
    "            if root <= 0 or dpsBackJump[root] == -1: return\n",
    "            if dpsBackJump[root] > 0: return\n",
    "            dpsBackJump[root] = step\n",
    "            if root == x: return\n",
    "            dp(root + a, step + 1)\n",
    "        \n",
    "        def dp(root: int, step: int):\n",
    "            if root > end or dps[root] == -1: return\n",
    "            if dps[root] > 0: return\n",
    "            dps[root] = step\n",
    "            if root == x: return\n",
    "            dp(root + a, step + 1)\n",
    "            dpBackJump(root - b, step + 1)\n",
    "\n",
    "        dp(a, 1)\n",
    "\n",
    "        if dps[x] == dpsBackJump[x] == 0: return -1\n",
    "        if dps[x] > 0 and dpsBackJump[x] > 0: return min(dps[x], dpsBackJump[x])\n",
    "        return dps[x] if dps[x] > 0 else dpsBackJump[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if a > b:\n",
    "            max_ = x + b\n",
    "        else:\n",
    "            max_ = max(max(forbidden)+a+b,x)\n",
    "        f = [[inf, inf] for _ in range(max_ + 1)]\n",
    "        forbidden = set(forbidden)\n",
    "        def dfs(p, d, t):\n",
    "            '''\n",
    "            forward d = 1\n",
    "            back d = 0\n",
    "            '''\n",
    "            if f[p][d] != inf or p in forbidden:\n",
    "                return\n",
    "            f[p][d] = t\n",
    "            if p == x:\n",
    "                return\n",
    "            fp, bp = p + a, p - b\n",
    "            if fp <= max_:\n",
    "                dfs(fp, 1, t+1)\n",
    "            if bp > 0 and d != 0:\n",
    "                dfs(bp, 0, t+1)\n",
    "\n",
    "        dfs(0, 1, 0)\n",
    "        #print(f)\n",
    "        ans = min(f[x])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        end = x + (a + b) * 3\n",
    "        # end = x + a * b\n",
    "        dps = [1_000_000_007] * (end + 1)\n",
    "        dpsBackJump = [1_000_000_007] * (end + 1)\n",
    "        \n",
    "        for ban in forbidden:\n",
    "            # if ban <= end: dps[ban] = -1\n",
    "            if ban <= end: dpsBackJump[ban] = dps[ban] = -1\n",
    "        \n",
    "        # def dp(root: int, step: int, isBackJump: bool):\n",
    "        #     if root < 0 or root > end or dps[root] == -1: return\n",
    "        #     # if dps[root] > 0 and dps[root] < step: return\n",
    "        #     if dps[root] <= step: return\n",
    "        #     dps[root] = step\n",
    "        #     dp(root + a, step + 1, False)\n",
    "        #     if not isBackJump: dp(root - b, step + 1, True)\n",
    "\n",
    "        def dpBackJump(root: int, step: int):\n",
    "            if root < 0 or root > end or dpsBackJump[root] == -1: return\n",
    "            if dpsBackJump[root] <= step: return\n",
    "            dpsBackJump[root] = step\n",
    "            dp(root + a, step + 1)\n",
    "        \n",
    "        def dp(root: int, step: int):\n",
    "            if root < 0 or root > end or dps[root] == -1: return\n",
    "            if dps[root] <= step: return\n",
    "            dps[root] = step\n",
    "            dp(root + a, step + 1)\n",
    "            dpBackJump(root - b, step + 1)\n",
    "\n",
    "        dp(0, 0)\n",
    "\n",
    "        res = min(dps[x], dpsBackJump[x])\n",
    "        return res if res < 1_000_000_007 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        self.key = -1\n",
    "        \n",
    "        def dfs(num, cnt, back):\n",
    "            if self.key < 0 and 0 <= num <= 6000:  # # 6000是往右探索的最大值，x最大为2000\n",
    "                if num == x:  # 第一次遍历到 x时的次数即为结果，暂存结果，不再递归\n",
    "                    self.key = cnt  \n",
    "                    return\n",
    "                if num+a not in forbidden:\n",
    "                    forbidden.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归\n",
    "                    dfs(num+a, cnt+1, 0)\n",
    "                if num-b not in forbidden and back != 1:  # 若back为1说明上次就是往后跳的\n",
    "                    dfs(num-b, cnt+1, 1)\n",
    "                \n",
    "        dfs(0, 0, 0)\n",
    "        return self.key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        self.key=-1       \n",
    "        forbidden=set(forbidden)\n",
    "\n",
    "        def find(count,p,flag):\n",
    "            if self.key<0 and 0<=p<=6000:\n",
    "                if p == x:\n",
    "                    self.key = count\n",
    "                    return\n",
    "                if p+a not in forbidden:#向前\n",
    "                    forbidden.add(p+a)\n",
    "                    \n",
    "                    find(count+1,p+a,True)\n",
    "                if flag and p-b not in forbidden:#后退\n",
    "                    \n",
    "                    find(count+1,p-b,False)\n",
    "\n",
    "        find(0,0,False)\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        self.key = -1\n",
    "        \n",
    "        def dfs(num, cnt, back):\n",
    "            if self.key < 0 and 0 <= num <= 6000:  # # 6000是往右探索的最大值，x最大为2000\n",
    "                if num == x:  # 第一次遍历到 x时的次数即为结果，暂存结果，不再递归\n",
    "                    self.key = cnt  \n",
    "                    return\n",
    "                if num+a not in forbidden:\n",
    "                    forbidden.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归\n",
    "                    dfs(num+a, cnt+1, 0)\n",
    "                if num-b not in forbidden and back != 1:  # 若back为1说明上次就是往后跳的\n",
    "                    dfs(num-b, cnt+1, 1)\n",
    "                \n",
    "        dfs(0, 0, 0)\n",
    "        return self.key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        # s = set(forbidden)\n",
    "        # s1 = set()\n",
    "        # lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        # def dfs(i,flag):\n",
    "        #     if i == x:\n",
    "        #         return 0\n",
    "        #     if i in s or (i,flag) in s1 or i < lower or i > upper:\n",
    "        #         return inf\n",
    "        #     s1.add((i,flag))\n",
    "        #     if flag:\n",
    "        #         return 1 + dfs(i + a,False)\n",
    "        #     else:\n",
    "        #         return 1 + min(dfs(i + a,False),dfs(i - b,True))\n",
    "        # ans = dfs(0,False)\n",
    "        # if ans == inf:\n",
    "        #     return -1\n",
    "        # else:\n",
    "        #     return ans\n",
    "        s = set(forbidden)\n",
    "        visited = set()\n",
    "        left = 0\n",
    "        right = max(max(forbidden) + a,x) + b\n",
    "        def dfs(i,flag):\n",
    "            if i == x:\n",
    "                return 0\n",
    "            if i in s or (i,flag) in visited or i < left or i > right:\n",
    "                return inf\n",
    "            visited.add((i,flag))\n",
    "            if flag:\n",
    "                return 1 + dfs(i + a,False)\n",
    "            else:\n",
    "                return 1 + min(dfs(i + a, False),dfs(i - b, True))\n",
    "        res = dfs(0,False)\n",
    "        if res == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        s = set(forbidden)\n",
    "        visited = set()\n",
    "        left = 0\n",
    "        right = max(max(forbidden) + a,x) + b\n",
    "        def dfs(i,flag):\n",
    "            if i == x:\n",
    "                return 0\n",
    "            if i in s or (i,flag) in visited or i < left or i > right:\n",
    "                return inf\n",
    "            visited.add((i,flag))\n",
    "            if flag:\n",
    "                return 1 + dfs(i + a,False)\n",
    "            else:\n",
    "                return 1 + min(dfs(i + a, False),dfs(i - b, True))\n",
    "        res = dfs(0,False)\n",
    "        if res == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        limit = max(max(forbidden) + a, x) + b\n",
    "        forbidden_set = set(forbidden)\n",
    "        min_jump_num = 1000000000\n",
    "        vivited = set()\n",
    "\n",
    "        def dfs(cur_pos, is_last_back, cur_jump_num):\n",
    "            nonlocal min_jump_num\n",
    "            nonlocal vivited\n",
    "            if cur_pos in forbidden_set or cur_pos < 0 or cur_jump_num > min_jump_num or cur_pos > limit:\n",
    "                return\n",
    "\n",
    "            if (cur_pos, is_last_back) in vivited:\n",
    "                return\n",
    "\n",
    "            if cur_pos == x:\n",
    "                min_jump_num = min(cur_jump_num, min_jump_num)\n",
    "                return\n",
    "            \n",
    "            vivited.add((cur_pos, is_last_back))\n",
    "\n",
    "            dfs(cur_pos + a, False, cur_jump_num + 1)\n",
    "\n",
    "            if not is_last_back:\n",
    "                dfs(cur_pos - b, True, cur_jump_num + 1)\n",
    "        \n",
    "        dfs(0, False, 0)\n",
    "\n",
    "        return min_jump_num if min_jump_num != 1000000000 else - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q = deque()\n",
    "        q.append((0,0,0))\n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        while q:\n",
    "            pos,time,ok = q.popleft()\n",
    "            if pos == x:\n",
    "                return time\n",
    "            if pos+a <= 1e5 and pos+a not in forbidden and pos+a not in vis:\n",
    "                q.append((pos+a,time+1,0))\n",
    "                vis.add(pos+a)\n",
    "            if pos-b >= 0 and pos-b not in forbidden and pos-b not in vis and ok == 0:\n",
    "                q.append((pos-b,time+1,1))\n",
    "                # vis.add(pos-b)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        def backtrack(i, k):\n",
    "            if i == x:\n",
    "                return 0\n",
    "            if i in forbidden or i in visited:\n",
    "                return float(\"inf\")\n",
    "            if (i, k) not in memo:\n",
    "                visited.add(i)\n",
    "                l = r = float(\"inf\")\n",
    "                if i <= mostR:\n",
    "                    r = backtrack(i + a, 1)\n",
    "                if k > 0 and i >= b:\n",
    "                    l = backtrack(i - b, 0)\n",
    "                memo[(i, k)] = 1 + min(l, r)\n",
    "                visited.remove(i)\n",
    "            return memo[(i, k)]\n",
    "\n",
    "        mostR = max(x, max(forbidden)) + b\n",
    "        visited = set()\n",
    "        memo = {}\n",
    "        return backtrack(0, 1) if backtrack(0, 1) != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        N = 6005\n",
    "        st = [True] * N\n",
    "        mp = [[-1 for i in range(2)] for i in range(N)]\n",
    "\n",
    "        def dfs(idx: int, u: int) -> int:\n",
    "            if idx == x:\n",
    "                return 0\n",
    "            if mp[idx][u] != -1:\n",
    "                return mp[idx][u]\n",
    "            res = N\n",
    "            if idx + a < N and st[idx + a]:\n",
    "                st[idx + a] = False\n",
    "                res = min(res, 1 + dfs(idx + a, 0))\n",
    "            if idx - b >= 0 and st[idx - b] and u < 1:\n",
    "                res = min(res, 1 + dfs(idx - b, 1))\n",
    "            mp[idx][u] = res\n",
    "            return res\n",
    "        \n",
    "        for e in forbidden:\n",
    "            st[e] = False\n",
    "        return dfs(0, 0) if dfs(0, 0) < N else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        @lru_cache(None)\n",
    "        def dfs(index, if_back):\n",
    "            nonlocal forbidden\n",
    "            if index == x:\n",
    "                return 0\n",
    "            res = 10**6\n",
    "            if index + a not in forbidden and index + a <= 2000 + a + b:\n",
    "                forbidden.add(index + a)\n",
    "                res = min(res, 1 + dfs(index + a, False))\n",
    "                forbidden.remove(index + a)\n",
    "            if not if_back:\n",
    "                if index - b not in forbidden and index - b > 0:\n",
    "                    forbidden.add(index - b)\n",
    "                    res = min(res, 1 + dfs(index - b, True))\n",
    "                    forbidden.remove(index - b)\n",
    "            return res\n",
    "        t = dfs(0, False)\n",
    "        return t if (t < 10 ** 6) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        f = max(forbidden)\n",
    "        upper = max(f + a + b, x + b)\n",
    "        @lru_cache(None)\n",
    "        def dfs(index, if_back):\n",
    "            nonlocal forbidden\n",
    "            if index == x:\n",
    "                return 0\n",
    "            res = 10**6\n",
    "            if index + a not in forbidden and index + a <= upper:\n",
    "                forbidden.add(index + a)\n",
    "                res = min(res, 1 + dfs(index + a, False))\n",
    "                forbidden.remove(index + a)\n",
    "            if not if_back:\n",
    "                if index - b not in forbidden and index - b > 0:\n",
    "                    forbidden.add(index - b)\n",
    "                    res = min(res, 1 + dfs(index - b, True))\n",
    "                    forbidden.remove(index - b)\n",
    "            return res\n",
    "        t = dfs(0, False)\n",
    "        return t if (t < 10 ** 6) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        q,visited=deque([[0,1,0]]),set([0])\n",
    "        lower,upper=0,50000\n",
    "        forbidden=set(forbidden)\n",
    "        while q:\n",
    "            nowposition,nowtoward,step=q.popleft()\n",
    "            if nowposition==x:\n",
    "                return step\n",
    "            nextposition=nowposition+a\n",
    "            nexttoward=1\n",
    "            if lower<=nextposition<=upper and nextposition*nexttoward not in visited and nextposition not in forbidden:\n",
    "                q.append([nextposition,nexttoward,step+1])\n",
    "                visited.add(nextposition*nexttoward)\n",
    "            if nowtoward==1:\n",
    "                nextposition=nowposition-b\n",
    "                nexttoward=-1\n",
    "                if lower<=nextposition<=upper and nextposition*nexttoward not in visited and nextposition not in forbidden:\n",
    "                    q.append([nextposition,nexttoward,step+1])\n",
    "                    visited.add(nextposition*nexttoward)\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        '''\n",
    "        BFS和DFS两种，「求最短次数更适合用BFS，每层是一跳，找到解就停。」\n",
    "        为啥不用DP？一开始想到是DP，不过因为此处可以向前也可以向后调，递推公式没法写了。。\n",
    "        关于上界：要区分a>b等情况，比较复杂，直接设置值域可以\n",
    "\n",
    "        自己写了dfs（只想到了dfs。。）有些cornercase，算了，直接看答案的吧\n",
    "        '''\n",
    "        # BFS\n",
    "        max_right = 99999\n",
    "        forbidden = set(forbidden) # 未来搜过的地方也加进去\n",
    "        que = collections.deque()\n",
    "        que.append((0,0,False))\n",
    "        while que:\n",
    "            cur,cnt,from_back = que.popleft()\n",
    "            if cur == x: # BFS的优势，先找到的解就是层数最少的\n",
    "                return cnt \n",
    "            if cur + a < max_right and cur+a not in forbidden:\n",
    "                forbidden.add(cur+a) # 搜过的地方不搜了\n",
    "                que.append((cur+a,cnt+1,False))\n",
    "            if not from_back and cur-b >0 and cur-b not in forbidden:\n",
    "                # forbidden.add(cur-b) 这里不可，因为回退到cur-b时，无法覆盖前进到cur-b再后退到cur-2b的情况\n",
    "                que.append((cur-b,cnt+1,True))\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if x % 2 and (a % 2 == 0 and b % 2 == 0):\n",
    "            return -1\n",
    "        forbidden_set = set(forbidden)\n",
    "        visited = set()\n",
    "\n",
    "        upper = 0\n",
    "        if a == b:\n",
    "            upper = x\n",
    "        if a > b:\n",
    "            upper = x + b\n",
    "        else:\n",
    "            upper = max(max(forbidden)+a+b, x)\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(cur: int, cnt: int, last: int = 0) -> int:\n",
    "            print(cur, cnt)\n",
    "            if (cur in forbidden_set \n",
    "                or cur < 0 \n",
    "                or (cur, last) in visited\n",
    "                or cur > upper):\n",
    "                return -1\n",
    "            if cur == x:\n",
    "                return cnt\n",
    "            \n",
    "            visited.add((cur, last))\n",
    "            ans1, ans2 = -1, -1\n",
    "            ans1 = dfs(cur + a, cnt + 1, 1)# 上一次没有向左走\n",
    "            if last != -1:\n",
    "                ans2 = dfs(cur - b, cnt + 1, -1)\n",
    "            \n",
    "            if ans1 == -1:\n",
    "                return ans2\n",
    "            if ans2 == -1:\n",
    "                return ans1\n",
    "            return min(ans1, ans2)\n",
    "\n",
    "\n",
    "        \n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        h = [(0, 0)]\n",
    "        visited = set()\n",
    "        while h:\n",
    "            n, p = heappop(h)\n",
    "            if p == x:\n",
    "                return n\n",
    "            if p in visited:\n",
    "                continue\n",
    "            visited.add(p)\n",
    "            if 0 <= p + a < 114514 and p + a not in forbidden:\n",
    "                heappush(h, (n + 1, p + a))\n",
    "                if 0 <= p + a - b < 114514 and p + a - b not in forbidden:\n",
    "                    heappush(h, (n + 2, p + a - b))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        \n",
    "  \n",
    "        upper=max(max(forbidden) + a, x) + b\n",
    "        forbidden=set(forbidden)\n",
    "        visited=set()\n",
    "        # @cache\n",
    "        def dp(i,way): #way=1 上一次是往前跳 way=-1 上一次往后跳\n",
    "            if i==x:\n",
    "                return 0\n",
    "            if i>upper:\n",
    "                return inf\n",
    "            if i<0:\n",
    "                return inf\n",
    "            if i in forbidden:\n",
    "                return inf\n",
    "            if way==1:\n",
    "                t1,t2=inf,inf\n",
    "                if (i+a,1) not in visited:\n",
    "                    visited.add((i+a,1))\n",
    "                    t1=1+dp(i+a,1)\n",
    "                if (i-b,-1) not in visited:\n",
    "                    visited.add((i-b,-1))\n",
    "                    t2=1+dp(i-b,-1)\n",
    "                return min(t1,t2)\n",
    "            else:\n",
    "                if (i+a,1) in visited:\n",
    "                    return inf\n",
    "                visited.add((i+a,1))\n",
    "                return 1+dp(i+a,1)\n",
    "        ans=dp(0,1)\n",
    "        if ans== inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        f = set(forbidden)\n",
    "        mx = max(max(f), x)\n",
    "        # mx = max(max(forbidden) + a, x) + b\n",
    "        def dfs(xn, s, fb): \n",
    "            if xn in f or xn<0 or xn> 6001:\n",
    "                return inf\n",
    "            if xn == x: \n",
    "                return s    \n",
    "            if fb != 1:\n",
    "                f.add(xn)\n",
    "                return min(dfs(xn+a, s+1, 0), dfs(xn-b, s+1, 1))\n",
    "            else:\n",
    "                return dfs(xn+a, s+1, 0)\n",
    "        \n",
    "        ans = dfs(0, 0, 0)\n",
    "        return ans if ans != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        self.res = 10**9 + 7\n",
    "        # memo = dict()\n",
    "        visited = set()\n",
    "        def recurse(pos, cnt, returnFlag):\n",
    "            if pos < 0  or pos > 6000:\n",
    "                return\n",
    "            if pos == x:\n",
    "                self.res = cnt\n",
    "                return\n",
    "            # if pos in memo:\n",
    "            #     memo[pos] = min(memo[pos], cnt)\n",
    "            # else:\n",
    "            #     memo[pos] = cnt\n",
    "            if pos + a not in forbidden and pos + a not in visited:\n",
    "                visited.add(pos + a)\n",
    "                recurse(pos + a, cnt + 1, 0)\n",
    "            if pos - b not in forbidden and pos - b not in visited and returnFlag != 1:\n",
    "                recurse(pos - b, cnt + 1, 1)\n",
    "        recurse(0, 0, 0)\n",
    "        # if x in memo:\n",
    "        #     return memo[x]\n",
    "        return self.res if self.res != 10**9 + 7 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if a>=b:\n",
    "            j = x+b\n",
    "        else:\n",
    "            j = max(max(forbidden)+a+b,x)\n",
    "        forbidden = set(forbidden)\n",
    "        @cache\n",
    "        def dfs(i,j,t):\n",
    "            res = 0\n",
    "            if i > j or i<0:\n",
    "                return inf\n",
    "            if i == x  :\n",
    "                return 0\n",
    "            if i in forbidden:\n",
    "                return inf\n",
    "            forbidden.add(i)\n",
    "            if t:\n",
    "                res = dfs(i+a,j,0)+1\n",
    "            else:\n",
    "                res = min(dfs(i+a,j,0),dfs(i-b,j,1))+1\n",
    "            forbidden.remove(i)\n",
    "            return res\n",
    "        res = dfs(0,j,0)\n",
    "        return -1 if res > 99999 else res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        res = inf\n",
    "        st = set(forbidden)\n",
    "        def dfs(cur: int, times: int, sign: bool):\n",
    "            if cur < 0 or cur > 6000: return\n",
    "            if cur == x:\n",
    "                nonlocal res\n",
    "                res = min(res, times)\n",
    "                return\n",
    "            if cur + a not in st:\n",
    "                st.add(cur + a)\n",
    "                dfs(cur + a, times + 1, False)\n",
    "            if not sign and cur - b not in st:\n",
    "                dfs(cur - b, times + 1, True)\n",
    "        dfs(0, 0, False)\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        res = inf\n",
    "        falg = [[0,0] for i in range(10000)]\n",
    "        \n",
    "        def dfs(cur_num,left_time,jump_time):\n",
    "            nonlocal res\n",
    "            # print(cur_num)\n",
    "            if cur_num>6000 or cur_num<0:return\n",
    "            if cur_num in forbidden:\n",
    "                return\n",
    "            if left_time>1:\n",
    "                return\n",
    "            if cur_num==x:\n",
    "                res = min(res,jump_time)\n",
    "            if falg[cur_num][0]==0:\n",
    "                if left_time==0:\n",
    "                    falg[cur_num][0]=1\n",
    "                falg[cur_num][1] = jump_time\n",
    "                dfs(cur_num+a,0,jump_time+1)\n",
    "                dfs(cur_num-b,left_time+1,jump_time+1)\n",
    "            else:\n",
    "                if falg[cur_num][1]<=jump_time:\n",
    "                    return\n",
    "                else:\n",
    "                    falg[cur_num][1] = jump_time\n",
    "                    dfs(cur_num+a,0,jump_time+1)\n",
    "                    dfs(cur_num-b,left_time+1,jump_time+1)\n",
    "            return\n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        dfs(0,0,0)\n",
    "        if res!=inf:\n",
    "            return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        '''\n",
    "            forbidden建成一个哈希表，便于查询，\n",
    "        '''\n",
    "        set_ = set(forbidden) # 障碍物的位置\n",
    "        vis = set() # 记录已经访问过的点\n",
    "        MAX = max([a, b, x] + forbidden)\n",
    "        @cache\n",
    "        def f(i: int, left_cnt: int) -> int: # i表示当前位置，left_cnt 表示上一步是否往左跳了1步\n",
    "            if i == x:\n",
    "                return 0\n",
    "            if i > MAX + a + b: # 最右边界 \n",
    "                return inf\n",
    "            vis.add(i)\n",
    "            ans = inf\n",
    "            if left_cnt == 0 and i - b >= 0 and (i - b) not in set_ and (i - b) not in vis: # 往左跳\n",
    "                ans = f(i - b, left_cnt + 1)\n",
    "            if (i + a) not in set_ and (i + a) not in vis: # 往右跳\n",
    "                ans = min(ans, f(i + a, 0))\n",
    "            vis.remove(i)\n",
    "            return ans + 1\n",
    "        ans = f(0, 0)\n",
    "        return - 1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        p = [[0] * 2 for i in range(2000 + a + x + b + 3)]\n",
    "        def d(i, f):\n",
    "            if i < 0 or i in forbidden or i > 2000 + a + b + x + 1:return 1e5\n",
    "            if i == 0: return 0\n",
    "            if p[i][f]: return 1e5\n",
    "            else:p[i][f] = 1\n",
    "            if f:\n",
    "                return d(i - a, 0) + 1\n",
    "            else:\n",
    "                return min(d(i - a, 0), d(i + b, 1)) + 1\n",
    "        ans = d(x, 0)\n",
    "        if ans > 1e4: return -1\n",
    "        else: return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        upper = max(max(forbidden) + a, x) + b\n",
    "        forbidden = set(forbidden)\n",
    "        visited = set()\n",
    "        @cache\n",
    "        def rec(p:int, is_back:int):\n",
    "            # print(p,is_back)\n",
    "            if p == x:\n",
    "                return 0\n",
    "            if (p,is_back) in visited or p in forbidden or p > upper:\n",
    "                return -1\n",
    "\n",
    "            visited.add((p,is_back))\n",
    "\n",
    "            front = back = -1\n",
    "            if not is_back and p > b:\n",
    "                back = rec(p-b,1)\n",
    "            front = rec(p+a,0)\n",
    "            \n",
    "            if front == -1 and back == -1:\n",
    "                return -1\n",
    "            elif back == -1:\n",
    "                return front + 1\n",
    "            elif front == -1:\n",
    "                return back + 1\n",
    "            return min(front,back) + 1\n",
    "\n",
    "        return rec(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        upper = max(max(forbidden) + a, x) + b\n",
    "        forbidden = set(forbidden)\n",
    "        visited = set()\n",
    "        @cache\n",
    "        def rec(p:int, is_back:int):\n",
    "            # print(p,is_back)\n",
    "            if p == x:\n",
    "                return 0\n",
    "            if (p,is_back) in visited or p in forbidden or p > upper:\n",
    "                return -1\n",
    "\n",
    "            visited.add((p,is_back))\n",
    "\n",
    "            front = back = -1\n",
    "            if not is_back and p > b:\n",
    "                back = rec(p-b,1)\n",
    "            front = rec(p+a,0)\n",
    "            \n",
    "            if front == -1 and back == -1:\n",
    "                return -1\n",
    "            elif back == -1:\n",
    "                return front + 1\n",
    "            elif front == -1:\n",
    "                return back + 1\n",
    "            return min(front,back) + 1\n",
    "\n",
    "        return rec(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        \n",
    "        '''\n",
    "        N = 2009 \n",
    "        INF = 99999999999\n",
    "        dp = [INF] * N\n",
    "        dp[0] = 0\n",
    "        \n",
    "        bfs = [[0,\"a\"]] \n",
    "        nums = 0 \n",
    "        while len(bfs) > 0: \n",
    "            nums += 1\n",
    "            temp_bfs = []\n",
    "            for step in bfs:\n",
    "                \n",
    "                next_step = step[0] + a\n",
    "                if (next_step) not in forbidden and next_step < N  : \n",
    "                    if ( nums  <= dp[next_step] ): \n",
    "                        dp[next_step] = nums\n",
    "                        if next_step == x:\n",
    "                            return nums\n",
    "                        \n",
    "                        temp_bfs.append([next_step, 'a'])      \n",
    "                if step[1] == \"a\":\n",
    "                    next_step = step[0] - b\n",
    "                    if (next_step) not in forbidden and next_step > 0 and next_step < N  :\n",
    "                        if (dp[next_step] == INF):\n",
    "                            dp[next_step] = nums\n",
    "                            if next_step == x:\n",
    "                                return nums\n",
    "                            temp_bfs.append([next_step, 'b']) \n",
    "            bfs = temp_bfs   \n",
    "        return -1\n",
    "        '''\n",
    "        N = 10009\n",
    "\n",
    "        self.ans = -1\n",
    "        OK  =[[0,0] for _ in range(N)]\n",
    "        Num = [0xfff ] * N\n",
    "\n",
    "\n",
    "        def  DFS(pos,steps,Type):\n",
    "            if pos>=N or pos<0 or pos in forbidden:\n",
    "                return\n",
    "            if OK[pos][Type] == 1:\n",
    "                return\n",
    "\n",
    "            OK[pos][Type] = 1\n",
    "            Num[pos] = min(Num[pos],steps)\n",
    "\n",
    "            #走a\n",
    "            DFS(pos+a,steps+1,0)\n",
    "\n",
    "            #走b\n",
    "            if Type == 0:\n",
    "                DFS(pos-b,steps+1,1)\n",
    "\n",
    "\n",
    "        DFS(0,0,0)\n",
    "        if OK[x][0] or OK[x][1]:\n",
    "            return Num[x]\n",
    "        else:\n",
    "            return -1\n",
    "                      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden=set(forbidden)\n",
    "        f=max(max(forbidden) + a, x) + b\n",
    "        forward_seen=set()\n",
    "        back_seen=set()\n",
    "        @cache\n",
    "        def dfs(i,back):\n",
    "            if back:\n",
    "                if i in back_seen:\n",
    "                    return inf\n",
    "                back_seen.add(i)\n",
    "            if not back:\n",
    "                if i in forward_seen:\n",
    "                    return inf\n",
    "                forward_seen.add(i)\n",
    "            if i==x:\n",
    "                return 0\n",
    "            if i>f or i<0 or i in forbidden:\n",
    "                return inf\n",
    "            if not back:\n",
    "                res1=dfs(i+a,False)+1\n",
    "                res2=dfs(i-b,True)+1\n",
    "                return min(res1,res2)\n",
    "            else:\n",
    "                return dfs(i+a,False)+1\n",
    "        return dfs(0,False) if dfs(0,False)<inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        if not x:\n",
    "            return 0\n",
    "        f = set(forbidden)\n",
    "        q = deque([[0, 0, True]])\n",
    "        v = set((0, True))\n",
    "        while q:\n",
    "            pos, step, goback = q.popleft()\n",
    "            c = [[pos + a, True]]\n",
    "            if goback:\n",
    "                c.append([pos - b, False])\n",
    "            for nxt, back in c:\n",
    "                if nxt == x:\n",
    "                    return step + 1\n",
    "                if nxt < 0 or nxt in f or nxt > 50000 or (nxt, back) in v:\n",
    "                    continue\n",
    "                q.append([nxt, step + 1, back])\n",
    "                v.add((nxt, back))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        limit = max(max(forbidden) + a, x) + b\n",
    "        forbidden_set = set(forbidden)\n",
    "        min_jump_num = 1000000000\n",
    "        vivited = set()\n",
    "        @cache\n",
    "        def dfs(cur_pos, is_last_back, cur_jump_num):\n",
    "            nonlocal min_jump_num\n",
    "            nonlocal vivited\n",
    "            if cur_pos in forbidden_set or cur_pos < 0 or cur_jump_num > min_jump_num or cur_pos > limit:\n",
    "                return\n",
    "\n",
    "            if (cur_pos, is_last_back) in vivited:\n",
    "                return\n",
    "\n",
    "            if cur_pos == x:\n",
    "                min_jump_num = min(cur_jump_num, min_jump_num)\n",
    "                return\n",
    "            \n",
    "            vivited.add((cur_pos, is_last_back))\n",
    "\n",
    "            dfs(cur_pos + a, False, cur_jump_num + 1)\n",
    "\n",
    "            if not is_last_back:\n",
    "                dfs(cur_pos - b, True, cur_jump_num + 1)\n",
    "        \n",
    "        dfs(0, False, 0)\n",
    "\n",
    "        return min_jump_num if min_jump_num != 1000000000 else - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        s = set(forbidden)\n",
    "        s1 = set()\n",
    "        lower, upper = 0, max(max(forbidden) + a, x) + b\n",
    "        @cache\n",
    "        def dfs(i,flag):\n",
    "            if i == x:\n",
    "                return 0\n",
    "            if i in s or (i,flag) in s1 or i < lower or i > upper:\n",
    "                return inf\n",
    "            s1.add((i,flag))\n",
    "            if flag:\n",
    "                return 1 + dfs(i + a,False)\n",
    "            else:\n",
    "                return 1 + min(dfs(i + a,False),dfs(i - b,True))\n",
    "        ans = dfs(0,False)\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        visited = set()\n",
    "        def go(start, bcnt):\n",
    "            # print(start)\n",
    "            if start == x:\n",
    "                return 0\n",
    "            if (start, bcnt) in visited or start in forbidden or start < 0 or start > 6000:\n",
    "                return math.inf\n",
    "            visited.add((start, bcnt))\n",
    "            \n",
    "            # ra = go(start+a, 0)\n",
    "            # rb = go(start-b, 1)\n",
    "            if bcnt == 0:\n",
    "                return 1 + min(go(start+a, 0), go(start-b, 1))\n",
    "            else:\n",
    "                return 1 + go(start+a, 0)\n",
    "        res = go(0, 0)\n",
    "        return res if res is not None and res != math.inf else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        # 达到x的前一步（x - a, x + b）\n",
    "        # 到达x+b的前一步（x + b - a） \n",
    "        from functools import lru_cache\n",
    "        visited = set()\n",
    "        mx = float('inf') \n",
    "\n",
    "        @lru_cache(None)\n",
    "        def do(pos):\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            elif pos < 0 or pos in forbidden or pos in visited or pos > 6000:\n",
    "                return mx\n",
    "            else:\n",
    "                visited.add(pos)\n",
    "                res = do(pos - a) + 1\n",
    "                if pos + b not in forbidden and pos + b not in visited:\n",
    "                    res = min(res, do(pos + b - a) + 2)\n",
    "                visited.remove(pos)\n",
    "                return res\n",
    "        return -1 if do(x) == mx else do(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        vis = set((b, x) for b in forbidden for x in (0, 1))\n",
    "        st = deque()\n",
    "        # 0 表示向右，1 表示向左\n",
    "        st.append((0, 0, 0))\n",
    "        while st:\n",
    "            cur, prev, step = st.popleft()\n",
    "            if cur == x:\n",
    "                return step\n",
    "            elif cur + a == x:\n",
    "                return step + 1\n",
    "            if cur < 10 * (x + a + b) and (cur + a, 0) not in vis:\n",
    "                st.append((cur + a, 0, step + 1))\n",
    "                vis.add((cur + a, 0))\n",
    "            if prev != 1 and cur - b > 0 and (cur - b, 1) not in vis:\n",
    "                st.append((cur - b, 1, step + 1))\n",
    "                vis.add((cur - b, 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        fb = set(forbidden)\n",
    "        found = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == 0: return 0\n",
    "            if i < 0 or i in fb or i in found or i > 6000:\n",
    "                return float('inf')\n",
    "            found.add(i)\n",
    "            res = min(dfs(i-a) + 1, dfs(i - a + b) + 2 if i + b not in fb else inf)\n",
    "            found.remove(i)\n",
    "            return res\n",
    "        r = dfs(x)\n",
    "        return -1 if r == float('inf') else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        fob = set(forbidden)\n",
    "        largest = 6000\n",
    "        calculating = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def do(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            elif x < 0 or x in fob or x in calculating or x > largest:\n",
    "                return float('inf')\n",
    "            else:\n",
    "                calculating.add(x)  # 为了防止计算x的时候, 后面又算回来需要知道x, 成环了\n",
    "                res = min(do(x-a)+1, do(x-a+b)+2 if x+b not in forbidden else inf)\n",
    "                calculating.remove(x)\n",
    "                return res\n",
    "\n",
    "        return -1 if do(x) == float('inf') else do(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        fob = set(forbidden)\n",
    "        largest = 6000\n",
    "        calculating = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def do(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            elif x < 0 or x in fob or x in calculating or x > largest:\n",
    "                return float('inf')\n",
    "            else:\n",
    "                calculating.add(x)  # 为了防止计算x的时候, 后面又算回来需要知道x, 成环了\n",
    "                res = min(do(x-a)+1, do(x-a+b)+2 if x+b not in forbidden else inf)\n",
    "                calculating.remove(x)\n",
    "                return res\n",
    "\n",
    "        return -1 if do(x) == float('inf') else do(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        fob = set(forbidden)\n",
    "        largest = 6000\n",
    "        calculating = set()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def do(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            elif x < 0 or x in fob or x in calculating or x > largest:\n",
    "                return float('inf')\n",
    "            else:\n",
    "                calculating.add(x)  # 为了防止计算x的时候, 后面又算回来需要知道x, 成环了\n",
    "                res = min(do(x-a)+1, do(x-a+b)+2 if x+b not in forbidden else inf)\n",
    "                calculating.remove(x)\n",
    "                return res\n",
    "\n",
    "        return -1 if do(x) == float('inf') else do(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(y):\n",
    "            if y == 0:\n",
    "                return 0\n",
    "            if y < 0 or y in forbidden or y > 6100 or y in v:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            v.add(y)\n",
    "            res = min(dfs(y - a) + 1, (dfs(y + b - a) + 2 )if y + b not in forbidden else float(\"inf\"))\n",
    "            v.remove(y)\n",
    "            return res\n",
    "            \n",
    "        forbidden = set(forbidden)\n",
    "        v = set()\n",
    "        res = dfs(x)\n",
    "        return -1 if res == float('inf') else res\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbid = set(forbidden)\n",
    "        largest = 6000\n",
    "        calculating = set()\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            elif x<0 or x in forbid or x in calculating or x >largest:\n",
    "                return float('inf')\n",
    "            else:\n",
    "                calculating.add(x)\n",
    "                res = min(dfs(x-a)+1, dfs(x-a+b)+2 if x+b not in forbid else inf)\n",
    "                calculating.remove(x)\n",
    "                return res\n",
    "        \n",
    "        return -1 if dfs(x) == float('inf') else dfs(x)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:\n",
    "        forbidden = set(forbidden)\n",
    "        if not x:\n",
    "            return 0\n",
    "        if a in forbidden:\n",
    "            return -1\n",
    "        step = 0\n",
    "        q = deque()\n",
    "        q.append((a, False))\n",
    "        vis = set()\n",
    "        vis.add((a, False))\n",
    "        l = 5 * 10 ** 4 + 7\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                i, back = q.popleft()\n",
    "                if i == x:\n",
    "                    return step + 1\n",
    "                if not back and i - b > 0 and (i - b, True) not in vis and i - b not in forbidden:\n",
    "                    q.append((i - b, True))\n",
    "                    vis.add((i - b, True))\n",
    "                if i + a < l and (i + a, False) not in vis and i + a not in forbidden:\n",
    "                    q.append((i + a, False))\n",
    "                    vis.add((i + a, False))\n",
    "            step += 1\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
